package com.sunny.structure.lineartable.singlelinked;

/**
 * 单链表
 *
 * @author Sunny
 * @date 2020/4/27
 */
public class ListNode {
    public int value;
    public ListNode next;

    public ListNode(int value) {
        this.value = value;
    }

    /**
     * 头节点插入
     *
     * @param head 头节点
     * @param newHead 新头节点
     */
    public static void headInsert(ListNode head, ListNode newHead) {
        ListNode old = head;
        head = newHead;
        head.next = old;
    }

    /**
     * 尾节点插入
     *
     * @param tail 尾节点
     * @param newTail 新尾节点
     */
    public static void tailInsert(ListNode tail, ListNode newTail) {
        ListNode old = tail;
        tail = newTail;
        tail.next = null;
        old.next = tail;
    }

    /**
     * 遍历
     *
     * @param head 头节点
     */
    public static void traverse(ListNode head) {
        while (head != null) {
            System.out.print(head.value + " ");
            head = head.next;
        }
        System.out.println();
    }

    /**
     * 查找 value 所在链表的顺序
     *
     * @param head 头节点
     * @param value 要查找的值
     */
    public static int find(ListNode head, int value) {
        int index = -1;
        int count = 0;
        while (head != null) {
            if (head.value == value) {
                index = count;
                return index;
            }
            count++;
            head = head.next;
        }
        return index;
    }

    /**
     * 在 p 节点后面插入 s 节点
     *
     * @param p 插入节点的前一个节点
     * @param s 待插入的节点
     */
    public static void insert(ListNode p, ListNode s) {
        ListNode next = p.next;
        p.next = s;
        s.next = next;
    }

    /**
     * 删除 q 节点
     *
     * @param head 链表头节点
     * @param q 待删除的节点
     */
    public static void delete(ListNode head, ListNode q) {
        /*
        * 如果是双向链表, 直接可以找到 q 的上一个节点, 把上一个节点的 next 指向 q 的next即可删除 q 节点
        * 但由于是单链表, 我们不知道 q 节点的上一个节点是谁
        * 所以采用的方法是将 q 节点的下一个节点值赋予 q ,在将 q 的下一个节点删除, 就相当于删除了 q 节点
        */
        if (q != null && q.next != null) {
            ListNode p = q.next;
            q.value = p.value;
            //删除q.next
            q.next = p.next;
        }else if (q != null) {
            //删除最后一个节点的情况
            while (head != null) {
                //连续删除的情况下会出错, 尾节点的地址值与之前定义的不一致,因为上面通过赋值的操作将尾节点替换了
                if (head.next != null && head.next == q) {
                    head.next = null;
                    break;
                }
                head = head.next;
            }
        }
    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        node1.next = node2;
        node2.next = node3;

        System.out.println("-----------init order------------");
        traverse(node1);

        System.out.println("-----------headInsert------------");
        ListNode node4 = new ListNode(4);
        headInsert(node1, node4);
        traverse(node4);

        System.out.println("-----------insert node5------------");
        ListNode node5 = new ListNode(5);
        insert(node3, node5);
        traverse(node4);

        System.out.println("-----------tailInsert------------");
        ListNode node6 = new ListNode(6);
        tailInsert(node3, node6);
        traverse(node4);

        System.out.println("-----------find------------");
        System.out.println(find(node4, 3));

        System.out.println("-----------delete node3------------");
        delete(node4, node3);
        traverse(node4);

        //注意这里会出错
        System.out.println("-----------delete node6------------");
        delete(node4, node6);
        traverse(node4);
    }
}
